package bill.study.algorithms.treesGraphs;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class CreateBSTFromPreOrder {
	
	public static void main(String [] arr){
		System.out.println("Hello world");
	}

	/** create a BST from a preorder traversed elements in an array. **/

	static class Node {
		int val;
		Node left;
		Node right;

		Node(int v) {
			this.val = v;
		}
	}

	public static Node createBST(int[] arr) {
		if (arr == null) {
			throw new IllegalArgumentException("arr cannot be null.");
		}

		if (arr.length == 0) {
			return null;
		}

		boolean mark[] = new boolean[arr.length];
		for (int i = 0; i < mark.length; i++) {
			mark[i] = false;
		}

		Map<Node, Integer> map = new HashMap<Node, Integer>();
		Node result = new Node(arr[0]);
		map.put(result, 0);
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(result);

		while (!queue.isEmpty()) {
			Node curr = queue.remove();
			int i = map.get(curr);

			// find the left node
			Node left = null;
			if (arr[i + 1] < arr[i] && (!mark[i + 1])) {
				left = new Node(arr[i + 1]);
				map.put(left, i + 1);
				mark[i + 1] = true;
				queue.add(left);
			}

			curr.left = left;

			Node right = null;

			boolean found = false;
			int j;
			for (j = i + 1; j < arr.length && !mark[j]; j++) {
				if (arr[j] >= arr[i]) {
					found = true;
					break;
				}
			}

			if (found) {
				right = new Node(arr[j]);
				map.put(right, j);
				mark[j] = true;
				queue.add(right);
			}

			curr.right = right;
		}

		return result;
	}
}
